#include<vector>
#include<iostream>

using namespace std;


void mergesort(vector<int> & vec, vector<int>& tmp , int begin,int end)
{
    if(begin>=end) return;

    int mid = (begin+end)>>1;
    int low =begin,lend=mid,rlow=mid+1,rend =end;

    mergesort(tmp,vec,low,lend);
    mergesort(tmp,vec,rlow,rend);

    int cpoyIndex = low;

    while(low<=lend&&rlow<=rend)
    {
        tmp[cpoyIndex++] = vec[low]>vec[rlow]?vec[rlow++]:vec[low++];
    }
    while(low<=lend)
    {
        tmp[cpoyIndex++] = vec[low++];
    }
    while(rlow<=rend)
    {
        tmp[cpoyIndex++]= vec[rlow++];
    }
}

void sort(vector<int> &vec)
{

    vector<int> tmp(vec);
    mergesort(vec,tmp,0,vec.size()-1);
    //vec.assign(tmp.begin(),tmp.end());
}

int main()
{
    vector<int> vec={9,8,5,4,3,7,1};
    sort(vec);
    for(const auto & i:vec)
    {
    cout<< i<<"\n";
    }
}
